package everydayone.generateParenthesis;

import java.util.ArrayList;
import java.util.List;

/**
 * @Date 2020/04/09
 * @author 王光浩
 * @Thinking 使用递归
 * @Analysis 时间复杂度O（好大），空间复杂（好大）
 */
public class MyMethodOne {
	public List<String> generateParenthesis(int n) {
		List<String> ret=new ArrayList<String>();
		if(n==0) return ret;
		//获取深度为 n-1 的所有可能有效括号组合
		for(int i=0;i<n;i++) {
			List<String> now=generateParenthesis(i);
			List<String> next=generateParenthesis(n-i-1);
			int sizeNow=now.size();
			int	sizeNext=next.size();
			if(sizeNow==0 && sizeNext==0) ret.add("()");
			else if(sizeNow==0)
				for(String tem:next) {
					ret.add("()"+tem);
				}
			else if(sizeNext==0)
				for(String tem:now) {
					ret.add("("+tem+")");
				}
			else
				for(int k=0;k<sizeNow;k++) {
					for(int j=0;j<sizeNext;j++)	ret.add("("+now.get(k)+")"+next.get(j));
				}
		}
		return ret;
    }
}
